package com.tgy.tree01;

import java.util.Comparator;

/**
 * @Author: tgy
 * @Date: 12/2/20 10:18 AM
 */
public class BinarySearchTree<E> extends BinaryTree<E> {

    private Comparator<E> comparator;

    public BinarySearchTree() {

        this(null);
    }

    public BinarySearchTree(Comparator<E> comparator) {
        this.comparator = comparator;
    }

    @Override
    public void add(E e) {

        if (root == null) {

            root = new Node<>(e,null);
            size++;
            return;
        }

        Node<E> node = root, parentNode = null;
        int cpmResult = 0;
        while (node != null) {

            parentNode = node;
            cpmResult = cmp(e,node.element);

            if (cpmResult < 0) {

                node = node.left;
            }else if (cpmResult > 0) {

                node = node.right;
            }else {

                return;
            }
        }

        Node<E> newNode = new Node<>(e, parentNode);

        if (cpmResult < 0) {

            // 左子树
            parentNode.left = newNode;
        }else if (cpmResult > 0) {

            parentNode.right = newNode;
        }

        size++;
    }

    @Override
    public E remove(E e) {

        // 查找e
        Node<E> node = elementOfNode(e);
        if (node == null) {
            // 不存在直接返回
            return null;
        }

        Node<E> rmNode = node;

        if (node.degree() == 2) {

            // 查找中序遍历下一个节点
            rmNode = findNextNode(node);
            if (rmNode != null) {

                E tmp = rmNode.element;
                rmNode.element = node.element;
                node.element  = tmp;
            }
        }

        Node<E> lastNode = rmNode.left != null?rmNode.left:rmNode.right;

        if (rmNode.parent == null) {

            root = lastNode;
            if (root != null) {
                root.parent = null;
            }
        }else {

            if (rmNode.isLeft()) {

                rmNode.parent.left = lastNode;
                if (lastNode != null) {

                    lastNode.parent = rmNode.parent;
                }
            }else {

                rmNode.parent.right = lastNode;

                if (lastNode != null) {

                    lastNode.parent = rmNode.parent;
                }

            }
        }

        size--;
        return rmNode.element;
    }

    protected Node<E> elementOfNode(E e) {

        if (root == null) {

            return null;
        }

        Node<E> node = root;

        while (node != null) {

            int cpmResult = cmp(e,node.element);

            if (cpmResult < 0) {

                node = node.left;
            }else if (cpmResult > 0) {

                node = node.right;
            }else {

                return node;
            }
        }

        return null;
    }

    /**
     * 中序遍历的下一个节点
     * @param node
     * @return
     */
    protected Node<E> findNextNode(Node<E> node) {

        Node<E> findNode = null;
        if (node.right != null) {

            // 往下找
            findNode = node.right;
            Node<E> preNode = null;
            while (findNode != null) {

                preNode = findNode;
                findNode = findNode.left;
            }

            return preNode;

        }else {

            // 往上找
            findNode = node;

            while (findNode != null && findNode.isRight()) {

                findNode = findNode.parent;
            }

            if (findNode != null) {

                findNode = findNode.parent;
            }
        }

        return findNode;
    }

    protected int cmp(E e1, E e2) {

        if (comparator != null) {

            return comparator.compare(e1,e2);
        }

        return ((Comparable)e1).compareTo(e2);
    }


}
